package offer.diff;

/**
 * https://leetcode-cn.com/problems/best-time-to-buy-and-sell-stock/description/?utm_source=LCUS&utm_medium=ip_redirect&utm_campaign=transfer2china
 * @author DengYuan2
 * @create 2021-03-04 20:13
 */
public class n_E_121 {
    public static void main(String[] args) {
        n_E_121 n = new n_E_121();
//        int[] prices = {7,1,5,3,6,4};
        int[] prices = {7,6,4,3,1};
        int res = n.maxProfit(prices);
        System.out.println(res);

    }

    /**
     * 我的：太慢-无法判断
     * @param prices
     * @return
     */
    public int maxProfit(int[] prices) {
        int max=0;
        int len =prices.length;
        for (int i = 0; i < len; i++) {
            int start=prices[i];
            for (int j = i+1; j < len; j++) {
                if (prices[j]>start){
                    max=Math.max(max,prices[j]-start);
                }
            }
        }
        return max;
    }

    public int maxProfit2(int[] prices){
        if (prices==null || prices.length==0){
            return 0;
        }
        int max=0;
        int curMin = prices[0];
        for (int i = 1; i < prices.length; i++) {
            curMin=Math.min(curMin,prices[i]);
            max=Math.max(max,prices[i]-curMin);

        }
        return max;
    }
}
